package com.banmoon.datastructure.BinaryTree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Objects;

@Data
@NoArgsConstructor
@AllArgsConstructor
public class BinaryTree {

    /**
     * 根节点
     */
    private TreeNode root;

    public BinaryTree(Integer value) {
        this.root = new TreeNode(value);
    }

    /**
     * 前序遍历
     */
    public void frontShow() {
        if (Objects.nonNull(root))
            root.frontShow();
    }

    /**
     * 后序遍历
     */
    public void middleShow() {
        if (Objects.nonNull(root))
            root.middleShow();
    }

    /**
     * 后序遍历
     */
    public void backShow() {
        if (Objects.nonNull(root))
            root.backShow();
    }

    /**
     * 判断是否存在
     * @param value
     * @return
     */
    public boolean contains(Integer value) {
        return Objects.nonNull(value) && root.contains(value);
    }

    /**
     * 删除
     * @param value
     */
    public TreeNode delete(int value) {
        TreeNode node = root;
        if (root==null || value==root.value) {
            root = null;
        } else {
            node = root.delete(value);
        }
        return node;
    }

    @Data
    @NoArgsConstructor
    public static class TreeNode {

        /**
         * 节点值
         */
        private Integer value;

        /**
         * 左节点
         */
        private TreeNode leftNode;

        /**
         * 右节点
         */
        private TreeNode rightNode;

        public TreeNode(Integer value) {
            this.value = value;
        }

        /**
         * 前序遍历
         */
        public void frontShow() {
            System.out.print(this.value);
            if (Objects.nonNull(this.leftNode))
                this.leftNode.frontShow();
            if (Objects.nonNull(this.rightNode))
                this.rightNode.frontShow();
        }

        /**
         * 中序遍历
         */
        public void middleShow() {
            if (Objects.nonNull(this.leftNode))
                this.leftNode.middleShow();
            System.out.print(this.value);
            if (Objects.nonNull(this.rightNode))
                this.rightNode.middleShow();
        }

        /**
         * 后序遍历
         */
        public void backShow() {
            if (Objects.nonNull(this.leftNode))
                this.leftNode.backShow();
            if (Objects.nonNull(this.rightNode))
                this.rightNode.backShow();
            System.out.print(this.value);
        }

        /**
         * 判断是否存在
         * @param value
         * @return
         */
        public boolean contains(Integer value) {
            boolean result = Objects.equals(this.value, value);
            if (!result && Objects.nonNull(this.leftNode))
                result = this.leftNode.contains(value);
            if (!result && Objects.nonNull(this.rightNode))
                result = this.rightNode.contains(value);
            return result;
        }

        /**
         * 删除
         * @param value
         * @return
         */
        public TreeNode delete(Integer value) {
            TreeNode node = null;
            if (Objects.nonNull(this.leftNode) && Objects.equals(this.leftNode.value, value)) {
                node = this.leftNode;
                this.leftNode = null;
                return node;
            }
            if (Objects.nonNull(this.rightNode) && Objects.equals(this.rightNode.value, value)) {
                node = this.rightNode;
                this.rightNode = null;
                return node;
            }
            if (Objects.nonNull(this.leftNode))
                node = this.leftNode.delete(value);
            if (node!=null && Objects.nonNull(this.rightNode))
                node = this.rightNode.delete(value);
            return node;
        }
    }

}

